The background description provided herein is for the purpose of generally presenting the context of the disclosure. Work of the presently named inventors, to the extent the work is described in this background section, as well as aspects of the description that may not otherwise qualify as prior art at the time of filing, are neither expressly nor impliedly admitted as prior art against the present disclosure.
Wireless sensor network (WSN) include a large number of sensor devices that are enabled with microchips that and are powered by limited energy source (e.g., small batteries). The sensor devices communicate with each other and other authorized devices via wireless links. As described by I. F. Akyildiz et. al. in “Wireless sensor networks: a survey,” Computer networks, vol. 38, no. 4, pp. 393-422, 2002, which is incorporated herein by reference in its entirety, WSNs are used widely in numerous applications including event monitoring, detection, control of environment, temperature sensing, humidity sensing, oil and gas exploration, toxic gas emission detection, traffic control, manufacturing and plant automation, military surveillance and the like.
As described by M. Dunbabin et. al. in “Data mulling over underwater wireless sensor networks using an autonomous underwater vehicle,” in Robotics and Automation, 2006. ICRA-IEEE, 2006, pp. 2091-2098, which is incorporated herein by reference in its entirety, sensors can be both static and autonomous based on the application domain. Hybrid sensor networks can be more energy efficient, wherein static sensors are only responsible for sensing data from environment and autonomous devices are responsible for relocation of the sensors,
Numerous techniques have been proposed for robot assisted sensor deployment. All such robot assisted techniques rely on the prior knowledge of their position i.e. through GPS and many of such techniques are not efficient enough to cover a region-of-interest (ROI) completely.
Another approach for sensor deployment is the Back-Tracking Deployment (BTD). The BTD approach considers a single robot which moves forward along a virtual grid with a predefined order of precedence until it reaches dead-end and then back-tracks to the nearest empty vertex. Further, molecule spreading concepts from physics are used to deploy sensors without the availability of global information. Self-deployment by density control (SDDC) technique focuses on the density control by each node for concurrent deployment of sensor nodes. The area density balance is maintained by forming clusters from the nodes. The SDDC technique has been shown to perform better than corresponding incremental self-deployment techniques.
Another approach for sensor deployment is the distributed hash table scheme as described by F. Dressler and M. Gerla, in “A framework for inter-domain routing in virtual coordinate based mobile networks,” Wireless networks, vol. 19, no. 7, pp. 1611-1626, 2013, and incorporated herein by reference in its entirety. In this work, the authors describe a technique of implementing inter-domain routing using appropriate indirections based on their virtual cord protocol (VCP). However, such a technique was shown to be inefficient in finding optimal routes over multiple transit networks. Accordingly, G. Fletcher et. al. in “Back-tracking based sensor deployment by a robot team,” in Sensor Mesh and Ad Hoc Communications and Networks (SECON), 2010 7th Annual IEEE Communications Society Conference on. IEEE, 2010, pp. 1-9, which is incorporated herein by reference in its entirety, proposed a new framework for optimized inter-domain routing. In particular, an ant colony optimization technique was implemented to optimize routes between multiple network domains.
Batalin and Sukhatme proposed the Least Recently Visited (LRV) algorithm in “Coverage, exploration and deployment by a mobile robot and communication network,” Telecommunication Systems, vol. 26, no. 2-4, pp. 181-196, 2004, which is incorporated herein by reference in its entirety, wherein already deployed sensors provide recommendations to robots for the direction to continue sensor placement. The algorithm produces full sensing coverage in a long run, but it incurs excessive robot movements to explore the ROI, and often faces termination problems.
Chang et al. designed a novel algorithm for sensor deployment in unpredictable region using the concept of spiral movement of robots in “Obstacle-resistant deployment algorithms for wireless sensor networks,” Vehicular Technology, IEEE Transactions on, vol. 58, no. 6, pp. 2925-2941, 2009 and “An obstacle-free and power-efficient deployment algorithm for wireless sensor networks,” Systems, Man and Cybernetics, Part A: Systems and Humans, IEEE Transactions on, vol. 39, no. 4, pp. 795-806, 2009, each of which is incorporated herein by reference in their entirety. The work by Chang proposes a Snake-Like Deployment (SLD) algorithm which may be of good contribution in the sensor deployment area as it focuses on deployment as well as the energy efficiency of the robots and sensors. However, a critical drawback of the algorithm is that it cannot guarantee full area coverage.
Santpal S and Krishnendu proposed two algorithms for efficient placement of sensors in a sensor field in their work of “Sensor placement for effective coverage and surveillance in distributed sensor networks”, IEEE 2003, vol. 3, which is incorporated herein by reference in its entirety. The main focus of their work was to develop an algorithm which would optimize the process of placing the minimum number of sensors with maximum coverage. The authors proposed a sensor detection model based on probabilistic mathematics according to which the probability of detection of a target by a sensor varies exponentially with the distance between the target and the sensor. However, the proposed framework proves to be unreliable due to the unreliable nature of the probabilistic results.
Howard et al. proposed in their work “An incremental self-deployment algorithm for mobile sensor networks,” Autonomous Robots, vol. 13, no. 2, pp. 113-126, 2002, which is incorporated herein by reference in its entirety, an incremental self-deployment strategy wherein a robot deploys the sensors in an unknown environment, one at a time and incrementally retrieves the next sensor location information from a central controller based on previously deployed sensor. However, this approach is very expensive and non-robust as the entire processing for the sensor position is done by the centralized controllers which would be highly computationally expensive. Also, if the central controller fails, then the entire ROI would be disconnected.
Wang et al. proposed a greedy solution for placing the sensor devices in a certain region for maximum coverage in their work, “Robot-assisted sensor network deployment and data collection,” Computational Intelligence in Robotics and Automation, 2007. CIRA 2007. International Symposium on. IEEE, 2007, pp. 467-472, which is incorporated herein by reference in its entirety. The main drawback of this solution was that it was GPS based framework that wouldn't work in the absence of a positioning system. Further, the maximum coverage problem was not solved as they only considered a fixed number of points called interest points.
Li et al. proposed in their work “An extended virtual force-based approach to distributed self-deployment in mobile sensor networks,” International Journal of Distributed Sensor Networks, vol. 2012, 2012, which is incorporated herein by reference in its entirety, an extended virtual force-based approach in distributed self-deployment of mobile sensor networks where their work covered the self-deployment of mobile sensor networks with stochastic distribution of nodes. The authors extended the VFA algorithm to achieve sensor deployment.
Movement-assisted sensor deployment provides optimal solution while deploying sensors from an initial unbalanced state to a balanced state. Various parameters such as traveled distance, number of moves and the like can be optimized with either centralized or localized methods. One Hungarian-algorithm based centralized and one movement based localized SMART (Scan-based Movement-Assisted Sensor Deployment) is used to further extend SMART and detect communication holes in sensor network in.
Tuna et al. proposed an algorithm in “An autonomous wireless sensor network deployment system using mobile robots for human existence detection in case of disasters,” Ad Hoc Networks, vol. 13, pp. 54-68, 2014, which is incorporated hereby by reference in its entirety. The algorithm named SLAM (Simultaneous Localization and Mapping) for sensor deployment by multiple robot agents to detect human existence in case of disasters. However, the process uses probabilistic method to determine the exploration map for the sensor deployment with the help of different sequence of landmarks from moving robots.
Broadcasting from static to mobile (BSM) protocol is used to provide seamless communication between source and destination without the necessity of connected dominating set (CDS), blind flooding, and hyper flooding. For instance in the work by I. Stojmenovic, “A general framework for broadcasting in static to highly mobile wireless ad hoc, sensor, robot and vehicular networks.” in ICPADS, S. Khuller, M. Purohit, and K. K. Sarpatwar, in “Analyzing the optimal neighborhood: Algorithms for budgeted and partial connected dominating set problems.” in SODA. SIAM, 2014, pp. 1702-1713 and in the work of M. Nandi, A. Nayak, B. Roy, and S. Sarkar, “Hypothesis testing and decision theoretic approach for fault detection in wireless sensor networks,” International Journal of Parallel, Emergent and Distributed Systems, pp. 1-24, 2014, and A. A. Khan, I. Stojmenovic, and N. Zaguia, “Parameterless broadcasting in static to highly mobile wireless ad hoc, sensor and actuator networks,” in Advanced Information Networking and Applications, 2008. AINA 2008. 22nd International Conference on. IEEE, 2008, pp. 620-627, each incorporated herein by reference in their entirety, timely delivery of warning in vehicular networks is shown without the usage of road maps. Note that the above described works can be employed among the mobile actuators for seamless coordination while deploying sensors in specific ROIs.
Total number of sensors required to provide minimum predefined lifetime for a certain network is determined with a NP-hard problem formulation by H. Liu et al. in “Minimum-cost sensor placement for required lifetime in wireless sensor-target surveillance networks,” Parallel and Distributed Systems, IEEE Transactions on, vol. 24, no. 9, pp. 1783-1796, 2013, which is incorporated herein by reference in its entirety. Lower bound on minimum number of sensors is calculated which demonstrated close-to-optimal solution.
Corke et al. mentioned one approach of sensor deployment using unmanned aerial vehicle (UAV) which was one of the early approaches in “Autonomous deployment and repair of a sensor network using an unmanned aerial vehicle,” Robotics and Automation, 2004. Proceedings. ICRA'04. 2004 IEEE International Conference on, vol. 4. IEEE, 2004, pp. 3602-3608, and is incorporated herein by reference in its entirety. In this framework, the authors used AVATAR (an autonomous helicopter) for sensor deployment and repairing. They deployed 50 sensor nodes using AVATAR on a grass field marked as 7-grid. They compared their result using both manual and autonomous mode. It was determined that two passes of AVATAR were required for deploying and subsequently repairing the sensor network.
Self-deployment of sensors (as described by M. Erdelj et al. in “Covering points of interest with mobile sensors,” Parallel and Distributed Systems, IEEE Transactions on, vol. 24, no. 1, pp. 32-43, 2013, which is incorporated herein by reference in their entirety), over a POI (Point of interest) and keeping inter-connection among the neighboring sensors is one of the complex issues. Additionally, keeping in touch with the base station is also a major constraint. POI deployment algorithm (PDA) is defined to overcome these issues by keeping communication with the neighboring sensors which are part of the relative neighborhood graph (RNG), chosen to provide global solution locally.
Sensor devices can act autonomously while collecting data in various forms as described by Younis and K. Akkaya in “Strategies and techniques for node placement in wireless sensor networks: A survey,” Ad Hoc Networks, vol. 6, no. 4, pp. 621-655, 2008, which is incorporated herein by reference in its entirety. The sensor devices have the capability to deliver the sensed data to some other location via wireless communication. In doing so would require an additional budget to keep the network up and alive for longer period of time. Researchers have come up with the hybrid approach so that sensors only have to get the data, other tasks will be carried out by the mobile robot devices. The mobile robots are responsible for deploying the sensors to some desired locations, replacing the faulty nodes, recharging the low charged sensors, data aggregation etc.
In particular, mobile actuators or robots are also equipped with different sensory devices like camera, laser beams, acoustic signals, local memory, communication devices etc. The equipment aids the robots to act autonomously for the sake of helping the sensors. However, it must be noted that wireless sensor and robot networks' first and foremost challenge is to deploy the sensors in their desired location so that sensors can easily perform their static job. On the other hand, robots perform the monitoring and maintenance task after deploying them to the calculated place (i.e., rather than being precomputed, the sensor locations are dynamically computed by the robot).
In most situations, static sensor placement may be feasible, but there are some mission critical applications which need mobile sensing. For instance, if we want to monitor some areas where it is impossible (if not difficult) for humans to access, then sensor deployment via robots is a good choice. Sometimes the area where the sensors need to be deployed is filled with obstacles and GPS maybe unavailable due to unavoidable reasons. Thus, there may be a requirement for a deployment mechanism which can deploy the sensors in the hazardous area without the need of GPS.
Accordingly, the present disclosure describes techniques of sensor deployment that address the above described drawbacks and limitations while providing for a scalable, robust, maximum-coverage, GPS-less and deadlock-free deployment framework.